﻿#include "stdafx.h"
#include "unittest.h"
#include "LongestPalindrome.h"
#include "Atoi.h"
#include "MergeTwoSortedLists.h"
#include "RemoveNthFromEnd.h"
#include "GenerateParenthesis.h"
#include "MergeKSortedLists.h"
#include "NextPermutation.h"
#include "LongestValidParentheses.h"
#include "SearchRotateLists.h"
#include "SearchSortedListsPos.h"
#include "DetectCycle.h"
#include "DailyTemperatures.h"
#include "SortLinkLists.h"
#include "MinStack.h"
#include "FindDuplicate.h"
#include "CountBits.h"
#include "MergeTrees.h"
#include "ListisPalindrome.h"
#include "DiameterOfBinaryTree.h"
#include "MoveZeroes.h"
#include "FindDisappearedNumbers.h"
#include "HammingDistance.h"

#include <assert.h>

using namespace std;

int main()
{
	algorithm::TestLongestPalindrome();
    algorithm::TestAtoi();
    algorithm::TestMergeTwoSortedLists();
    algorithm::TestRemoveNthFromEnd();
    algorithm::TestGenerateParenthesis();
    algorithm::TestMergeKSortedLists();
    algorithm::TestNextPermutation();
    algorithm::TestLongestValidParentheses();
    algorithm::TestSearchRotateLists();
    algorithm::TestSearchSortedListsPos();
    algorithm::TestDetectCycle();
    algorithm::TestDailyTemperatures();
    algorithm::TestSortLinkLists();
    algorithm::TestMinStack();
    algorithm::TestFindDuplicate();
    algorithm::TestCountBits();
    algorithm::TestMergeTrees();
    algorithm::TestListIsPalindrome();
    algorithm::TestDemeterOfBinaryTree();
    algorithm::TestMoveZeroes();
    algorithm::TestFindDisappearedNumbers();
    algorithm::TestHammingDistance();

	return 0;
}

namespace algorithm {
void TestLongestPalindrome()
{
	assert(CLongestPalindrome::From("babad") == "bab");
	assert(CLongestPalindrome::From("cbbd") == "bb");
}
void TestAtoi()
{
    assert(CAtoi::From("1f") == 1);
    assert(CAtoi::From("42") == 42);
    assert(CAtoi::From("   -042") == -42);
    assert(CAtoi::From("-0402") == -402);
    assert(CAtoi::From("1337c0d3") == 1337);
    assert(CAtoi::From("0-1") == 0);
    assert(CAtoi::From("words and 987") == 0);
    assert(CAtoi::From("+040234325435643532") == INT_MAX);
    assert(CAtoi::From("-03453453453403452") == INT_MIN);
    assert(CAtoi::From("-34534534534346457567658768678678685645634534534532523423423423434534503452") == INT_MIN);
    assert(CAtoi::From("-91283472332") == INT_MIN);
    assert(CAtoi::From("  0000000000012345678f") == 12345678);
    assert(CAtoi::From("-6147483648") == INT_MIN);
}

static ListNode* AllocListNode(const vector<int>& vec)
{
    ListNode head;
    ListNode* node = &head;
    for (auto val : vec) {
        node->next = new ListNode(val);
        node = node->next;
    }

    return head.next;
}

static void FreeListNode(ListNode* pNode)
{
    while (pNode) {
        auto next = pNode->next;
        delete pNode;
        pNode = next;
    }
}

static bool CompareListNode(ListNode* list1, const vector<int>& vec)
{
    vector<int> temp;
    ListNode head(0, list1);
    ListNode* node = &head;
    while (node->next) {
        temp.push_back(node->next->val);
        node = node->next;
    }
    if (temp.empty() && vec.empty())
    {
        return true;
    }

    return equal(temp.begin(), temp.end(), vec.begin(), vec.end());
}

void TestMergeTwoSortedLists()
{
    {
        ListNode* node1 = AllocListNode({1,2,4});
        ListNode* node2 = AllocListNode({ 3,5,6 });
        ListNode* result = CMergeTwoSortedLists::Merge(node1, node2);
        assert(CompareListNode(result, {1,2,3,4,5,6}));
        FreeListNode(node1);
        FreeListNode(node2);
        FreeListNode(result);
    }

    {
        ListNode* node1 = AllocListNode({ 0 });
        ListNode* node2 = AllocListNode({  });
        ListNode* result = CMergeTwoSortedLists::Merge(node1, node2);
        assert(CompareListNode(result, { 0 }));
        FreeListNode(node1);
        FreeListNode(node2);
        FreeListNode(result);
    }
}

void TestRemoveNthFromEnd()
{
    {
        ListNode* node1 = AllocListNode({ 1,2,3,4,5 });
        ListNode* result = CRemoveNthFromEnd::Remove(node1, 2);
        assert(CompareListNode(result, { 1,2,3,5 }));
        FreeListNode(result);
    }
    {
        ListNode* node1 = AllocListNode({ 1 });
        ListNode* result = CRemoveNthFromEnd::Remove(node1, 1);
        assert(CompareListNode(result, { }));
        FreeListNode(result);
    }
    {
        ListNode* node1 = AllocListNode({ 1,2 });
        ListNode* result = CRemoveNthFromEnd::Remove(node1, 1);
        assert(CompareListNode(result, { 1 }));
        FreeListNode(result);
    }
}

static bool CompareStringList(const vector<string>& src, const vector<string>& dst)
{
    if (src.size() != dst.size()) {
        return false;
    }
    if (src.empty()) {
        return true;
    }
    unordered_set<string> cache;
    for (auto& str : src) {
        cache.insert(str);
    }
    for (auto& str : dst) {
        if (cache.find(str) == cache.end()) {
            return false;
        }
    }

    return true;
}

void TestGenerateParenthesis()
{
    assert(CompareStringList(CGenerateParenthesis::Generate(1), { "()" }));
    assert(CompareStringList(CGenerateParenthesis::Generate(3), { "((()))","(()())","(())()","()(())","()()()" }));
}

void TestMergeKSortedLists()
{
    {
        ListNode* node1 = AllocListNode({ 1,4,5 });
        ListNode* node2 = AllocListNode({ 1,3,4 });
        ListNode* node3 = AllocListNode({ 2,6 });
        vector<ListNode*> vec = { node1, node2, node3 };
        ListNode* result = CMergeKSortedLists::Merge(vec);
        assert(CompareListNode(result, { 1,1,2,3,4,4,5,6 }));
        FreeListNode(result);
        FreeListNode(node1);
        FreeListNode(node2);
        FreeListNode(node3);
    }
    {
        vector<ListNode*> vec;
        ListNode* result = CMergeKSortedLists::Merge(vec);
        assert(CompareListNode(result, { }));
    }
    {
        ListNode* node1 = nullptr;
        vector<ListNode*> vec = { node1};
        ListNode* result = CMergeKSortedLists::Merge(vec);
        assert(CompareListNode(result, { }));
    }
}

void TestNextPermutation()
{
    {
        vector<int> nums = initializer_list<int>{ 1,2,3 };
        vector<int> rst = initializer_list<int>{ 1,3,2 };
        CNextPermutation::Next(nums);
        assert(equal(nums.begin(), nums.end(), rst.begin(), rst.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 3,2,1 };
        vector<int> rst = initializer_list<int>{ 1,2,3 };
        CNextPermutation::Next(nums);
        assert(equal(nums.begin(), nums.end(), rst.begin(), rst.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 4,5,2,6,3,1 };
        vector<int> rst = initializer_list<int>{ 4,5,3,1,2,6 };
        CNextPermutation::Next(nums);
        assert(equal(nums.begin(), nums.end(), rst.begin(), rst.end()));
    }
}

void TestLongestValidParentheses()
{
    assert(CLongestValidParentheses::Length("(()") == 2);
    assert(CLongestValidParentheses::Length(")()())") == 4);
    assert(CLongestValidParentheses::Length("") == 0);
    assert(CLongestValidParentheses::Length("())()()(()))()()") == 8);
    assert(CLongestValidParentheses::Length("(())(") == 4);
    assert(CLongestValidParentheses::Length("()(()") == 2);
}

void TestSearchRotateLists()
{
    {
        vector<int> nums = initializer_list<int>{ 4,5,6,7,0,1,2 };
        assert(CSearchRotateLists::Search(nums, 0) == 4);
    }
    {
        vector<int> nums = initializer_list<int>{ 4,5,6,7,0,1,2 };
        assert(CSearchRotateLists::Search(nums, 3) == -1);
    }
    {
        vector<int> nums = initializer_list<int>{ 1 };
        assert(CSearchRotateLists::Search(nums, 0) == -1);
    }
    {
        vector<int> nums = initializer_list<int>{ 1,3 };
        assert(CSearchRotateLists::Search(nums, 4) == -1);
    }
}

void TestSearchSortedListsPos()
{
    {
        vector<int> nums = initializer_list<int>{ 5,7,7,8,8,10 };
        vector<int> expect = initializer_list<int>{ 3,4 };
        auto result = CSearchSortedListsPos::Search(nums, 8);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 5,7,7,8,8,10 };
        vector<int> expect = initializer_list<int>{ -1,-1 };
        auto result = CSearchSortedListsPos::Search(nums, 6);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
    {
        vector<int> nums = initializer_list<int>{  };
        vector<int> expect = initializer_list<int>{ -1,-1 };
        auto result = CSearchSortedListsPos::Search(nums, 0);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 5,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,10 };
        vector<int> expect = initializer_list<int>{ 3,29 };
        auto result = CSearchSortedListsPos::Search(nums, 8);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
}

/** 
 * @brief 构造循环链表.
 * @param[in] vec 链表节点值
 * @param[in] pos 环起始位置，即链表尾节点next指针指向pos位置的链表节点，构造环
 */
static ListNode* AllocCycleListNode(const vector<int>& vec, int pos)
{
    if (vec.empty()) {
        return nullptr;
    }
    ListNode head;
    ListNode* node = &head;
    unordered_map<int, ListNode*> cache;
    int i = 0;
    for (auto val : vec) {
        node->next = new ListNode(val);
        cache[i++] = node->next;
        node = node->next;
    }

    // 构造环
    int size = vec.size();
    if (pos >= 0 && pos < size) {
        cache[size - 1]->next = cache[pos];
    }
    return head.next;
}

static void FreeCycleListNode(ListNode* pNode, int pos)
{
    int i = 0;
    unordered_map<int, ListNode*> cache;
    while (pNode) {
        if (cache.find(pos) != cache.end()) {
            break;
        }
        auto next = pNode->next;
        cache[i++] = pNode;
        delete pNode;
        pNode = next;
    }
}

void TestDetectCycle()
{
    {
        ListNode* node1 = AllocCycleListNode({ 3,2,0,-4 }, 0);
        ListNode* result = CDetectCycle::First(node1);
        assert(result == node1);
        FreeCycleListNode(node1, 0);
    }
    {
        ListNode* node1 = AllocListNode({ 3,2,0,-4 });
        ListNode* result = CDetectCycle::First(node1);
        assert(result == nullptr);
        FreeListNode(node1);
    }
}

void TestDailyTemperatures()
{
    {
        vector<int> nums = initializer_list<int>{ 73,74,75,71,69,72,76,73 };
        vector<int> expect = initializer_list<int>{ 1,1,4,2,1,1,0,0 };
        auto result = CDailyTemperatures::Calc(nums);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 30,40,50,60 };
        vector<int> expect = initializer_list<int>{ 1,1,1,0 };
        auto result = CDailyTemperatures::Calc(nums);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 30,60,90 };
        vector<int> expect = initializer_list<int>{ 1,1,0 };
        auto result = CDailyTemperatures::Calc(nums);
        assert(equal(expect.begin(), expect.end(), result.begin(), result.end()));
    }
}

void TestSortLinkLists()
{
    {
        ListNode* node1 = AllocListNode({ 4,2,1,3 });
        ListNode* result = CSortLinkLists::Sort(node1);
        assert(CompareListNode(result, {1,2,3,4}));
        FreeListNode(node1);
    }
    {
        ListNode* node1 = AllocListNode({ -1,5,3,4,0 });
        ListNode* result = CSortLinkLists::Sort(node1);
        assert(CompareListNode(result, { -1,0,3,4,5 }));
        FreeListNode(node1);
    }
    {
        ListNode* node1 = AllocListNode({  });
        ListNode* result = CSortLinkLists::Sort(node1);
        assert(result == nullptr);
        FreeListNode(node1);
    }
}

void TestMinStack()
{
    {
        CMinStack stack;
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        assert(stack.getMin() == -3);
        stack.pop();
        assert(stack.top() == 0);
        assert(stack.getMin() == -2);
    }
    {
        CMinStack stack;
        stack.push(INT_MAX);
        stack.push(INT_MIN);
        assert(stack.getMin() == INT_MIN);
        stack.pop();
        assert(stack.top() == INT_MAX);
        assert(stack.getMin() == INT_MAX);
    }
}

void TestFindDuplicate()
{
    {
        vector<int> nums = initializer_list<int>{ 1,3,4,2,2 };
        assert(CFindDuplicate::Find(nums) == 2);
    }
    {
        vector<int> nums = initializer_list<int>{ 3,1,3,4,2 };
        assert(CFindDuplicate::Find(nums) == 3);
    }
    {
        vector<int> nums = initializer_list<int>{ 3,3,3,3,3 };
        assert(CFindDuplicate::Find(nums) == 3);
    }
}

void TestCountBits()
{
    {
        vector<int> result = CCountBits::Count(2);
        assert((result == vector<int>{ 0,1,1 }));
    }
    {
        vector<int> result = CCountBits::Count(5);
        assert((result == vector<int>{ 0,1,1,2,1,2 }));
    }
}
static const int None = INT_MIN;
TreeNode* AllocTreeNode(const vector<int>& vec)
{
    if (vec.empty() || vec[0] == None) {
        return nullptr;
    }
    TreeNode* root = new TreeNode(vec[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < static_cast<int>(vec.size())) {
        auto node = q.front();
        q.pop();
        if (vec[i] != None) {
            node->left = new TreeNode(vec[i]);
            q.push(node->left);
        }
        i++;
        if (i < static_cast<int>(vec.size()) && vec[i] != None) {
            node->right = new TreeNode(vec[i]);
            q.push(node->right);
        }
        i++;
    }
    return root;
}

void FreeTreeNode(TreeNode* pNode)
{
    if (pNode == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(pNode);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
        delete node;
    }
}

bool CompareTreeNode(TreeNode* pNode1, TreeNode* pNode2)
{
    if (pNode1 == nullptr && pNode2 == nullptr) {
        return true;
    }
    if (pNode1 == nullptr || pNode2 == nullptr) {
        return false;
    }
    if (pNode1->val != pNode2->val) {
        return false;
    }
    return CompareTreeNode(pNode1->left, pNode2->left) &&
        CompareTreeNode(pNode1->right, pNode2->right);
}

void TestMergeTrees()
{
    {
        TreeNode* node1 = AllocTreeNode({ 1,3,2,5 });
        TreeNode* node2 = AllocTreeNode({ 2,1,3,None,4,None,7 });
        TreeNode* result = CMergeTrees::Merge(node1, node2);
        TreeNode* expect = AllocTreeNode({ 3,4,5,5,4,None,7 });
        assert(CompareTreeNode(result, expect));
        FreeTreeNode(node1);
        FreeTreeNode(node2);
        FreeTreeNode(result);
        FreeTreeNode(expect);
    }
    {
        TreeNode* node1 = AllocTreeNode({ 1,2,None,3 });
        TreeNode* node2 = AllocTreeNode({ 1,None,2,None,3 });
        TreeNode* result = CMergeTrees::Merge(node1, node2);
        TreeNode* expect = AllocTreeNode({ 2,2,2,3,None,None,3 });
        assert(CompareTreeNode(result, expect));
        FreeTreeNode(node1);
        FreeTreeNode(node2);
        FreeTreeNode(result);
        FreeTreeNode(expect);
    }
}

void TestListIsPalindrome()
{
    {
        ListNode* node1 = AllocListNode({ 1,2,2,1 });
        assert(CListIsPalindrome::Check(node1) == true);
        FreeListNode(node1);
    }
    {
        ListNode* node1 = AllocListNode({ 1,2 });
        assert(CListIsPalindrome::Check(node1) == false);
        FreeListNode(node1);
    }
    {
        ListNode* node1 = AllocListNode({ 1,2,3,2,1 });
        assert(CListIsPalindrome::Check(node1) == true);
        FreeListNode(node1);
    }
}

void TestDemeterOfBinaryTree()
{
    {
         TreeNode* node1 = AllocTreeNode({ 1,2,3,4,5 });
         assert(CDiameterOfBinaryTree::GetDiameter(node1) == 3);
         FreeTreeNode(node1);
    }
    {
        TreeNode* node1 = AllocTreeNode({ 1,2,3,4,5,None,None,6,None,7,None,8,9,10,None,11 });
        assert(CDiameterOfBinaryTree::GetDiameter(node1) == 7);
        FreeTreeNode(node1);
    }
    {
        TreeNode* node1 = AllocTreeNode({ 1,2 });
        assert(CDiameterOfBinaryTree::GetDiameter(node1) == 1);
        FreeTreeNode(node1);
    }
}

void TestMoveZeroes()
{
    {
        vector<int> nums = initializer_list<int>{ 0,1,0,3,12 };
        vector<int> expect = initializer_list<int>{ 1,3,12,0,0 };
        CMoveZeroes::Move(nums);
        assert(equal(nums.begin(),nums.end(), expect.begin(),expect.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 0 };
        vector<int> expect = initializer_list<int>{ 0 };
        CMoveZeroes::Move(nums);
        assert(equal(nums.begin(), nums.end(), expect.begin(), expect.end()));
    }
}

void TestFindDisappearedNumbers()
{
    {
        vector<int> nums = initializer_list<int>{ 4,3,2,7,8,2,3,1 };
        vector<int> expect = initializer_list<int>{ 5,6 };
        auto result = CFindDisappearedNumbers::Find(nums);
        assert(equal(result.begin(), result.end(), expect.begin(), expect.end()));
    }
    {
        vector<int> nums = initializer_list<int>{ 1,1 };
        vector<int> expect = initializer_list<int>{ 2 };
        auto result = CFindDisappearedNumbers::Find(nums);
        assert(equal(result.begin(), result.end(), expect.begin(), expect.end()));
    }
}

void TestHammingDistance()
{
    assert(CHammingDistance::Distance(1, 4) == 2);
    assert(CHammingDistance::Distance(3, 1) == 1);
}

}
